package leetcode.year2021.month10;

import java.util.ArrayList;
import java.util.List;

/**
 * 94. 二叉树的中序遍历
 */
public class _23_02inorderTraversal94 {
  public List<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> ans = new ArrayList<>();
    mediumOrderTraversal(root, ans);
    return ans;
  }

  private void mediumOrderTraversal(TreeNode root, ArrayList<Integer> ans) {
    if (root == null){
      return;
    }
    mediumOrderTraversal(root.left, ans);
    ans.add(root.val);
    mediumOrderTraversal(root.right,ans);
  }


  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

  /**
   * 输入：root = [1,null,2,3]
   * 输出：[1,3,2]
   * 示例 2：
   *
   * 输入：root = []
   * 输出：[]
   * 示例 3：
   *
   * 输入：root = [1]
   * 输出：[1]
   *
   * 来源：力扣（LeetCode）
   * 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
   * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
   */
}
